package leetcode_classic150;

import java.util.*;

public class Demo3 {


    // 125. 验证回文串
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        StringBuilder tmp = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (ch >= 'a' && ch <= 'z' || ch >= '0' && ch <= '9') tmp.append(ch);
        }

        for (int left = 0, right = tmp.length() - 1; left < right; left++, right--) {
            if (tmp.charAt(left) != tmp.charAt(right)) return false;
        }
        return true;
    }




    // 392. 判断子序列
    public boolean isSubsequence(String s, String t) {
        int n = s.length(), m = t.length();
        if (n > m) return false;

        int i = 0, j = 0;
        while (i < n && j < m) {
            for (; i < n && j < m && s.charAt(i) == t.charAt(j); i++, j++);
            j++;
        }
        return i == n;
    }




    // 11. 盛最多水的容器
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, max = 0;
        int v = 0;
        while(left < right) {
            int h = Math.min(height[left], height[right]);
            v = (right - left) * h;
            if(v > max) max = v;
            if(height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max;
    }



    // 135. 分发糖果
    public int candy(int[] ratings) {
        int n = ratings.length;
        if (n == 1) return 1;

        int[] f = new int[n];
        f[0] = ratings[0] > ratings[1] ? 2 : 1;
        for (int i = 1; i < n; i++) {
            f[i] = ratings[i] > ratings[i - 1] ? f[i - 1] + 1 : 1;
        }

        int[] g = new int[n];
        g[n - 1] = ratings[n - 1] > ratings[n - 2] ? 2 : 1;
        int ret = Math.max(f[n - 1], g[n - 1]);
        for (int i = n - 2; i >= 0; i--) {
            g[i] = ratings[i] > ratings[i + 1] ? g[i + 1] + 1 : 1;
            ret += Math.max(f[i], g[i]);
        }
        return ret;
    }





    // 15. 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> ret = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 2; ) {
            if (nums[i] > 0) break;         // nums[i] > 0，一定不存在三数之和等于0
            int sum = -nums[i], tmp = nums[i];

            for (int left = i + 1, right = n - 1; left < right; ) {
                if (nums[left] + nums[right] == sum) {
                    ret.add(Arrays.asList(nums[i], nums[left++], nums[right--]));
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[left] + nums[right] < sum) left++;
                else right--;
            }

            // 跳过相同的 i
            while (i < n - 2 && nums[i] == tmp) i++;
        }
        return ret;
    }




    // 209. 长度最小的子数组
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length, res = 0X3f3f3f3f;
        int sum = 0;
        for (int left = 0, right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                res = Math.min(res, right - left + 1);
                sum -= nums[left++];
            }
        }
        return res == 0X3f3f3f3f ? 0 : res;
    }




    // 3. 无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) return 0;
        boolean[] flag = new boolean[128];

        int ret = 0;
        for (int left = 0, right = 0; right < n; right++) {
            char ch = s.charAt(right);

            while (flag[ch]) {      // 如果前面已经出现则出栈
                flag[s.charAt(left++)] = false;
            }
            flag[ch] = true;        // 入栈
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }



    // 30. 串联所有单词的子串
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String,Integer> hash = new HashMap<>();         // 统计words中各单词出现的次数
        for (String word : words) hash.put(word, hash.getOrDefault(word, 0) + 1);
        int len = words[0].length(), n = s.length(), m = words.length;

        List<Integer> ret = new ArrayList<>();
        for (int i = 0; i < len ; i++) {
            Map<String,Integer> count = new HashMap<>();
            for (int left = i, right = i, valid = 0; right + len <= n; ) {
                String tmp = s.substring(right, right + len);
                right += len;
                count.put(tmp, count.getOrDefault(tmp, 0) + 1);         // 入栈
                if (hash.containsKey(tmp) && count.get(tmp) <= hash.get(tmp)) valid++;

                if (right - left == len * m) {
                    // 判断是否为串联子串
                    if (valid == m) ret.add(left);

                    String str = s.substring(left, left + len);
                    count.put(str, count.get(str) - 1);
                    if (hash.containsKey(str) && count.get(str) < hash.get(str)) valid--;
                    left += len;
                }
            }
        }
        return ret;
    }




    // 2810. 故障键盘
    public String finalString(String s) {
        StringBuilder tmp = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (ch != 'i') tmp.append(ch);
            else tmp = tmp.reverse();
        }
        return tmp.toString();
    }



    // 42. 接雨水
    public int trap(int[] height) {
        // 单调栈解法: 求下一个比当前位置大的元素
        Deque<Integer> stack  = new ArrayDeque<>();

        int ret = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                Integer mid = stack.pop();
                if (!stack.isEmpty()) {
                    Integer leftIndex = stack.peek();       // 左边第一个比当前位置大的元素的下标
                    Integer w = i - leftIndex - 1, h = Math.min(height[i], height[leftIndex]) - height[mid];
                    ret += w * h;
                }
            }
            stack.push(i);
        }
        return ret;
    }



    // 36. 有效的数独
    public boolean isValidSudoku(char[][] board) {
        boolean[][] row = new boolean[9][10], col = new boolean[9][10];
        boolean[][][] grid = new boolean[3][3][10];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int num = board[i][j] - '0';
                if (row[i][num] || col[j][num] || grid[i/3][j/3][num]) return false;
                row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
            }
        }
        return true;
    }




    // 54. 螺旋矩阵
    private List<Integer> res;
    public List<Integer> spiralOrder(int[][] matrix) {
        res = new ArrayList<>();
        int row = matrix.length, col = matrix[0].length;

        for (int i = 0, j = 0; res.size() < row * col; i++, j++) {
            search(matrix, i, j, row - i - 1, col - j - 1);
        }
        return res;
    }
    private void search(int[][] matrix, int x, int y, int row, int col) {
        // 首行搜索
        for (int j = y; j <= col; j++) res.add(matrix[x][j]);
        // 尾列搜索
        for (int i = x + 1; i <= row; i++) res.add(matrix[i][col]);

        if (x == row || y == col) return;

        // 尾行搜索
        for (int j = col - 1; j >= y; j--) res.add(matrix[row][j]);
        // 首列搜索
        for (int i = row - 1; i > x; i--) res.add(matrix[i][y]);
    }




    // 383. 赎金信
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] count = new int[26];
        for (char ch : magazine.toCharArray()) count[ch - 'a']++;

        for (char ch : ransomNote.toCharArray()) {
            if (--count[ch - 'a'] < 0) return false;
        }
        return true;
    }



    // 49. 字母异位词分组
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, Integer> map = new HashMap<>();
        List<List<String>> ret = new ArrayList<>();

        for (String s : strs) {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            String str = new String(arr);
            if (!map.containsKey(str)) {
                ret.add(new ArrayList<>());
                map.put(str, ret.size() - 1);
            }
            ret.get(map.get(str)).add(s);
        }

        return ret;
    }




    // 1. 两数之和
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if (map.containsKey(target - x)) return new int[]{i, map.get(target - x)};
            map.put(x, i);
        }
        return null;
    }



    // 56. 合并区间
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        if(intervals.length == 1) return intervals;
        int n = intervals.length;

        List<int[]> list = new ArrayList<>();
        for(int i = 0; i < n; ) {
            int start = intervals[i][0], end = intervals[i][1];
            while(i < n && end >= intervals[i][0]) {
                end = Math.max(end, intervals[i][1]);
                i++;
            }
            list.add(new int[]{start, end});
        }

        return list.toArray(new int[0][]);
    }



    // 20. 有效的括号
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();

        char[] arr = s.toCharArray();
        for(int i = 0; i < arr.length; i++) {
            char ch = arr[i];
            if(ch == '(' || ch == '[' || ch == '{') stack.push(ch);
            else {
                if(stack.isEmpty()) return false;
                char top = stack.peek();
                if(top == '{' && ch == '}' || top == '[' && ch == ']' || top == '(' && ch == ')') stack.pop();
                else return false;
            }
        }
        return stack.isEmpty();
    }


    // 219. 存在重复元素 II
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }




    // 202. 快乐数
    public boolean isHappy(int n) {
        int fast = convert(n), slow = n;
        while (fast != 1 && slow != 1 && fast != slow) {
            fast = convert(fast);
            fast = convert(fast);
            slow = convert(slow);
        }
        return fast == 1 || slow == 1;
    }
    private int convert(int n) {
        int res = 0;
        while (n > 0) {
            res += (n % 10) * (n % 10);
            n /= 10;
        }
        return res;
    }







}
